class Solution(object):
    def numIslands(self, grid):
        """
        :type grid: List[List[str]]
        :rtype: int
        """
        self.visited = []
        for _ in range(len(grid)):
            self.visited.append([False] * len(grid[0]))
        res = 0
        for i in range(len(grid)):
            for j in range(len(grid[i])):
                res = res + self.count_island(grid, i, j)
        return res

    def count_island(self, grid, i, j):
        if self.visited[i][j]:
            return 0
        self.visite_island(grid, i, j)
        print(str(i) + "----------" + str(j) )
        print(self.visited)
        if grid[i][j] == "0":
            return 0
        return 1

    def visite_island(self, grid, i, j):
        if i < 0 or j < 0 or i >= len(grid) or j >= len(grid[0]):
            return
        if self.visited[i][j]:
            return
        if grid[i][j] == "0":
            return
        print( 'visite_island#'  + str(i) + '####' + str(j))
        self.visited[i][j] = True
        for d in ((0, 1), (1, 0), (0, -1), (-1, 0)):
            print( 'from#'  + str(i) + '####' + str(j))
            self.visite_island(grid, i + d[0], j + d[1])
        print( str(i) + '####' + str(j) + ": " + str(grid[i][j]))

if __name__ == '__main__':
    print(Solution().numIslands(
        [["0","1","0"],
         ["1","0","1"],
         ["0","1","0"]]
    ))